//
// Created by Poyyo on 2021/6/11.
//

#include "Graph/GraphInListImpl.h"
#include <queue>

using namespace std;

void bfs_fun(GraphInListImpl &graph, queue<int> &queue, int id) {
    // 将id入队，并标记已经访问
    queue.push(id);
    graph.Select(id);
    // 当队列非空，则进入
    while (!queue.empty()) {
        // 获取队首结点的id
        auto visitId = queue.front();
        queue.pop();
        // 访问队首结点
        graph.Visit(visitId);
        // 队首结点
        auto visitVertex = graph.getList().find(visitId);
        // 邻接结点列表
        auto nodes = visitVertex->second.nodes;
        // 遍历邻接结点列表，将所有未访问的邻接结点入队
        while (nodes != nullptr) {
            // 如果该结点未被访问过，则入队，标记已经访问
            if (!(graph.getList().find(nodes->id)->second.vertex.isSelected())) {
                queue.push(nodes->id);
                graph.Select(nodes->id);
            }
            nodes = nodes->next;
        }
    }
}
/**
 * 广度优先遍历
 * @param graph
 */
void bfs(GraphInListImpl &graph) {
    queue<int> queue;
    auto &list = graph.getList();
    auto length = list.size();
    // 遍历所有的结点，如果没有被访问过则开始广度优先搜索算法
    for (int i = 1; i <= length; i++) {
        if (!(list.find(i)->second.vertex.isSelected())) {
            bfs_fun(graph, queue, i);
        }
    }
    cout << endl;
}

/*
1 2 2 4
2 1 4
3 0
4 1 3
 */
int main() {
    GraphInListImpl graphInList;
    graphInList.ToString();
    bfs(graphInList);
}